import javafx.util.Pair;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-09-12
 * Time: 15:25
 */
class Solution4 {
    public int widthOfBinaryTree(TreeNode root) {
        // 用数组模拟队列
        List<Pair<TreeNode,Integer>> q = new ArrayList<>();
        q.add(new Pair<TreeNode,Integer>(root,1));
        int ret = 0;

        while(!q.isEmpty()) {
            // 先更新一下这一层的宽度
            Pair<TreeNode,Integer> t1 = q.get(0);
            Pair<TreeNode,Integer> t2 = q.get(q.size()-1);
            ret = Math.max(ret,t2.getValue() - t1.getValue() + 1);

            // 让下一层进队 因为数组出队时间复杂度高 用这个tmp接收再替换
            List<Pair<TreeNode,Integer>> tmp = new ArrayList<>();
            for(Pair<TreeNode,Integer> t : q) {
                TreeNode node = t.getKey();
                int index = t.getValue();

                if(node.left != null) {
                    tmp.add(new Pair<TreeNode,Integer>(node.left,2 * index));
                }

                if(node.right != null) {
                    tmp.add(new Pair<TreeNode,Integer>(node.right,2 * index + 1));
                }
            }
            q = tmp;
        }
        return ret;
    }
}
